Computers use resources, such as memory, modems and printers, during the execution of computer programs. Many of these resources are only used periodically by any given computer program. For example, the amount of time a word processing application requires a printer to print documents is typically small relative to the amount of time that the word processing application is used to create documents. If the only process that had access to the printer was a single word processing application, the printer would remain idle most of the time.
To take full advantage of resources, computer networks have been developed in which processes running on many computer devices, or “nodes”, can share resources. Thus, instead of having to purchase one printer for every computer, users may purchase a single printer that may be connected to a network that has many computers. Processes on each computer on the network access the printer only when the processes require the printer.
Even though resources may be shared, as described above, many resources may not be used by more than one process at any given time. For example, most printers are unable to print more than one document at a time. Other resources, such as data blocks of a storage medium or tables stored on a storage medium, may be concurrently accessed in some ways (e.g. read) by multiple processes, but accessed in other ways (e.g. written to) by only one process at a time. Consequently, mechanisms have been developed which control access to resources.
One such mechanism is referred to as a lock. A lock is a data structure that indicates that a particular process has been granted certain rights with respect to the resource. There are many types of locks. Some types of locks may be shared by many processes, while other types of locks prevent any other locks to be granted on the same resource.
For example, ownership of a NULL mode lock on a table grants a process no permission to access the table in any manner. Ownership of a concurrent read lock grants a process permission to read the table, but does not guarantee that other processes are not concurrently writing to the table. Ownership of a protected read lock grants a process permission to read the table and guarantees that no other process is concurrently writing to the table. Ownership of a concurrent write lock grants a process permission to write to the table, but does not guarantee that another process is not also writing to the table. Ownership of a protected write lock grants a process permission to write to the table and guarantees that another process is not also writing to the table. Ownership of an exclusive mode lock grants a process permission to do anything with a table, and guarantees that no other process is performing any operation on the table.
Due to the various permissions and guarantees associated with these locks, certain lock combinations are not allowed. For example, if a process owns an exclusive mode lock on a resource, then no other process can be granted any lock other than a NULL mode lock. If a process owns a protected write lock, then no other process may be granted an exclusive mode lock, a protected write lock, a protected read lock or a concurrent write lock. If a process owns a protected read lock, then no other process may be granted an exclusive mode lock, a protected write lock or a concurrent write lock. If a process owns a concurrent write lock, then no other process may be granted an exclusive mode lock, a protected write lock, or a protected read lock. If a process owns a concurrent read lock, then no other process may be granted an exclusive mode lock.
A category of lock that may be held by more than one process at a time is referred to as a share lock. For example, two processes can hold concurrent read locks on the same resource at the same time, so concurrent read locks are share locks. For the purposes of explanation, the following description shall refer to exclusive mode locks, share locks, and NULL mode locks.
Before a process can perform an operation on a resource, the process is required to obtain a lock that grants to the process the right to perform the desired operation on the resource. To obtain a lock, a process transmits a request for the lock to a lock manager. A lock manager is a process that is responsible for granting, queuing, and keeping track of locks on one or more resources. To manage the use of resources in a network system, lock managers are executed on one or more nodes in the network.
According to one prior art implementation, a lock manager implements two types of objects: a resource object and a lock. Resource objects are data structures that correspond to actual resources. An application that uses a lock manager establishes a mapping between actual resources and resource objects. Each resource object has two queues: a granted queue and a convert queue. The granted queue is an unordered list of locks that have been granted. The convert queue is a partially ordered list of locks that have been requested, but not yet granted. Typically, a request for a lock is actually a convert request, where a process holding a lock is requesting that the lock it holds be converted from one mode of lock to a different mode of lock.
Locks are data structures that identify a process and a lock mode. Lock managers attach locks to the grant queues of resource objects to indicate that the process identified in the lock has been granted a lock of the type indicated in the lock on the resource that corresponds to the resource object to which the lock is attached.
FIG. 1 is a block diagram illustrating a typical lock manager 106. Lock manager 106 is a process that is configured to manage a resource object 100 stored in a memory 108. The resource object includes a granted queue 102 and a convert queue 104. Lock manager 106 has attached three locks 110, 112 and 114 to the granted queue 102, and one convert request 130 to the convert queue 104.
All locks and convert requests have a process ID portion and a lock mode portion. The process ID portion 116 of lock 110 indicates that a process PROC_1 owns lock 110, and the lock mode portion 118 of lock 10 indicates that lock 110 is an exclusive lock. The process ID portion 120 of lock 112 indicates that lock 12 is owned by a process PROC_2, and the lock mode portion 122 of lock 112 indicates that lock 112 is a NULL mode lock. The process ID portion 124 of lock 114 indicates that lock 114 is owned by a process PROC_3, and the lock mode portion 126 of lock 114 indicates that lock 114 is a NULL lock. The process ID portion 132 of convert request 130 indicates that convert request 130 is associated with process PROC_4, and the lock mode portion 136 of convert request 130 indicates that PROC_4 currently holds a NULL mode lock on the resource. In addition to a lock mode portion 136, convert request 130 has a requested mode portion 134 that indicates that PROC_4 is requesting an exclusive mode lock.
Lock manager 106 has attached locks 110, 112 and 114 to granted queue 102, indicating that PROC_1 currently has exclusive ownership of the resource that corresponds to resource object 100. Lock manager 106 has attached convert request 130 to the convert queue 104, indicating that PROC_4 has requested but has not yet been granted an exclusive mode lock on the resource associated with resource object 100.
Information pertaining to any given resource may be stored in the resource object that corresponds to the resource. Each resource object is stored in the memory of a single node. The node on which a resource object is stored is referred to as the master node for the resource object.
According to one lock management approach, a process initially establishes a NULL mode lock on all resources that the process will possibly use. Then, when the process actually requires access to a resource, the process requests that its NULL mode lock be converted to a lock that grants to the process the rights to perform the desired operation.
For example, to delete a table, a process must obtain an exclusive mode lock on the resource object that corresponds to the table. To obtain the exclusive mode lock, the process transmits a message to the lock manager that controls the resource object that corresponds to the table. In the message, the process requests that its current NULL mode lock be converted to an exclusive mode lock. If no other process has requested a conversion, and if no currently granted locks would prevent the grant of an exclusive mode lock, then the current lock held by the requesting process is converted to an exclusive mode lock. Once the lock manager performs the requested conversion, the lock manager transmits a message to the requesting process to indicate that the requested conversion operation has been performed.
If a process requires access to read data from a table, the process must obtain a share lock. To obtain a share lock, the process requests the lock manager that controls the resource object that corresponds to the table to convert its current lock to a share lock. If no other process has requested a conversion, and if no currently granted locks would prevent the grant of a share lock, then the current lock held by the requesting process is converted to a share lock.
If an exclusive mode lock has already been granted for the table, then a share lock cannot be granted. Under these circumstances, the lock convert request is placed on the convert queue of the resource object. When the blocking process is ready to release its exclusive lock, the blocking process may send a lock downgrade request to the lock manager. The lock manager responds by converting the exclusive mode lock to a lesser lock that allows the grant of the share lock. The share lock is then granted by moving the share lock request from the requested queue to the granted queue and transmitting a message to the requesting process to inform the requesting process that the share lock has been granted.
The convert queue of a resource object is a partially ordered list that holds all outstanding (ungranted) lock requests. If any outstanding lock requests have not been granted, one of the ungranted lock requests will be at the “head” of the convert queue. Even if the currently granted locks do not prevent a lock manager from granting a particular lock request, the lock request is placed on the convert queue if the convert queue is not empty. This policy prevents “livelocks”, where one process cannot make progress in the system while other processes can.
It is not uncommon for many processes to concurrently hold share locks on a resource. The set of processes that hold share locks on a particular resource are collectively referred to herein as the “share lock holders”.
If one of the share lock holders (the “requester”) wants to convert to an exclusive mode lock, the requester has to first send a convert request to the master node of the resource. When the shared-to-exclusive request reaches the head of the convert queue in the master node of the resource, the master node sends downconvert request messages to all share lock holders asking them to downconvert or close their locks. The master node can only grant the exclusive lock to the requester after all share lock holders acknowledge to the master that they have downconverted their locks. Between the time the requester sends the upgrade request and the time that the exclusive lock is granted, the requester has to wait, and cannot start updating the resource or perform any subsequent work even though the requester already has a current copy of the resource in its cache.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.